package offer;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/
@FunctionalInterface
public interface Permute {
    List<List<Integer>> permute(int[] nums);
}

class PermuteImpl1 implements Permute{

    /**
     * 解法一： 分治法
     * @param nums
     * @return
     */
    @Override
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> numsArray = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            numsArray.add(nums[i]);
        }
        List<List<Integer>> ans = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        permuteHelper(stack,ans,numsArray);
        return ans;
    }
    private void permuteHelper(Stack<Integer> stack,List<List<Integer>> ans, List<Integer> numsArray){
        if(numsArray.isEmpty()){
            ans.add(stack.stream().collect(Collectors.toList()));
        }else{
            for (int i = 0; i < numsArray.size(); i++) {
                int currentElement = numsArray.get(i);
                List<Integer> copy = numsArray.stream().filter(element -> element != currentElement).collect(Collectors.toList());
                stack.add(currentElement);
                permuteHelper(stack,ans,copy);
                stack.pop();
            }
        }
    }
}

class PermuteImpl2 implements Permute{

    @Override
    public List<List<Integer>> permute(int[] nums) {
        boolean[] isVisited = new boolean[nums.length];
        List<List<Integer>> ans = new LinkedList<>();
        int[] stack = new int[nums.length];
        int top = 0;
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i] = false;
        }
        permuteHelper(nums,isVisited,ans,stack,top);
        return ans;
    }
    private void permuteHelper(int[] nums,boolean[] isVisited,List<List<Integer>> ans,int[] stack,int top){
        if(top == nums.length){
            List<Integer> item = new LinkedList<>();
            ans.add(item);
            for (int i = 0; i < stack.length; i++) {
                item.add(stack[i]);
            }
            return;
        }
        for (int j = 0; j < isVisited.length; j++) {
            if(!isVisited[j]){
                stack[top++] = nums[j];
                isVisited[j] = true;
                permuteHelper(nums,isVisited,ans,stack,top);
                top--;
                isVisited[j] = false;
            }
        }
        return;
    }
}
